/*  add_reducer.h                  -*-C++-*-
 *
 * Copyright (C) 2011, Intel Corporation
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in
 *     the documentation and/or other materials provided with the
 *     distribution.
 *   * Neither the name of Intel Corporation nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

/*
 * add_reducer.h
 *
 * Purpose: Reducer hyperobject to sum values
 */

#ifndef ADD_REDUCER_H_INCLUDED
#define ADD_REDUCER_H_INCLUDED

#ifndef __cplusplus
#   error add_reducer not yet implemented for C.
#endif

#include "reducer_ptr.h"

/* C++ Interface
 *
 * Classes: add_reducer_ptr<Type>
 *
 * Description:
 * ============
 * This component provides a reducer-type hyperobject representation
 * that allows adding values to a non-local variable using the +=, -=,
 * ++, --, +, and - operators.  A common operation when traversing a data
 * structure is to sum values into a non-local numeric variable.  When
 * Cilk parallelism is introduced, however, a data race will occur on
 * the variable holding the sum.  By replacing the variable with the
 * hyperobject defined in this component, the data race is eliminated.
 *
 * Usage Example:
 * ==============
 * Assume we wish to traverse an array of objects, performing an operation on
 * each object and accumulating the result of the operation into an integer
 * variable.
 *..
 *  int compute(const X& v);
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern X myArray[ARRAY_SIZE];
 *      // ...
 *
 *      int result = 0;
 *      for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          result += compute(myArray[i]);
 *      }
 *
 *      std::cout << "The result is: " << result << std::endl;
 *
 *      return 0;
 *  }
 *..
 * Changing the 'for' to a 'cilk_for' will cause the loop to run in parallel,
 * but doing so will create a data race on the 'result' variable.  The race is
 * solved by referencing 'result' through an 'add_reducer_ptr' hyperpointer.
 *..
 *  int compute(const X& v);
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern X myArray[ARRAY_SIZE];
 *      // ...
 *
 *      int result = 0;
 *      cilk::add_reducer_ptr<int> p_result(&result);
 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          *p_result += compute(myArray[i]);
 *      }
 *
 *      std::cout << "The result is: " << result << std::endl;
 *
 *      return 0;
 *  }
 *..
 *
 * Reading and writing the hyperobject:
 * ====================================
 * In the previous example, 'p_result' is a hyperpointer created from the
 * primary object, 'result'.  Reading or modifying 'result' directly produces
 * deterministic behavior only when performed before the first spawn after
 * creating 'p_result' or when all strands spawned since creating the
 * 'p_result' have been synced.  Using 'result' at other times is likely to
 * create a data race.
 *
 * Normally, in parallel execution, the value of 'result' should be modified
 * through 'p_result' using summing operators (+=, ++, etc.).  The value
 * represented by the current view of '*p_result' can be read and modified
 * without using the summing operators by means of the
 * 'get_value_for_current_strand' and 'set_value_for_current_strand'
 * functions, respectively.  As with most reducers,
 * 'set_value_for_current_strand' and 'get_value_for_current_strand' functions
 * may produce nondeterministic results if called in parallel code.  However,
 * the difference between two values of the same reducer read twice in the
 * same Cilk strand *is* typically deterministic (assuming the usual
 * relationship between operator '+' and operator '-' for the specified
 * 'Type'):
 *..
 *  int x = 0;
 *  cilk::add_reducer_ptr<int> p(&x);
 *  _Cilk_spawn func();
 *  int a = cilk::get_value_for_current_strand(*p);
 *  *p += 5;
 *  int b = cilk::get_value_for_current_strand(*p);
 *  assert(b - a == 5);
 *..
 *
 * Operations provided:
 * ====================
 * Given 'add_reducer_ptr' objects, x and y, the following are
 * valid statements:
 *..
 *  *x += 5;
 *  *x = *x + 5;
 *  *x -= 5;
 *  *y = *y - 5;
 *  ++*x;
 *  --*x;
 *  (*x)++;
 *  (*x)--;
 *  x = y;
 *..
 * The following are not valid expressions and will result in a run-time error
 * in a debug build:
 *..
 *  *x = *y;     // Cannot assign one reducer view to another
 *  *x = *y + 5; // Mixed reducers
 *  *x = 5 + *x; // operator+ is not necessarily commutative
 *  *x = 5 - *x; // Violates associativity
 *..
 * 
 * Requirements on the 'Type' parameter
 * ====================================
 *
 * The 'Type' parameter used to instantiate the 'add_reducer' class must
 * provide a += operator that is an associative mutating operator.
 * The default constructor for 'Type' must yield an additive identity, i.e.,
 * a value (such as integer zero) that, when added to any other value, yields
 * the other value.  If 'Type' also provides a -= operator, then subtraction
 * is also supported by this reducer. C++ integral types satisfy these
 * requirements.
 *
 * Note that C++ floating-point types do not support truly associative
 * addition in that (a + b) + c will exhibit different round-off error than 
 * a + (b + c).  For numbers of similar magnitude, however, a floating-point
 * 'add_reducer' may still be useful.
 */

namespace cilk 
{

/**
 * @brief A wrapper around type Type supporting only summing operations.
 *
 * An instantiation of add_reducer_view is the view type for an
 * add_reducer_ptr.  In order to prevent user errors, it wraps its
 * value type Type to allow only the operations consistent with the
 * associative operation for this reducer, i.e., addition.  For
 * example, add_reducer_view supports the operators += and ++, but not
 * *= because mixing multiplication with addition does not produce an
 * associative sequence of operations.
 */
template <typename Type>
class add_reducer_view 
{
    // Not copyable
    add_reducer_view(const add_reducer_view&);
    add_reducer_view& operator=(const add_reducer_view&);

    // "PRIVATE" HELPER CLASS     
    // temp_sum is the result type of the expression v + x, where v is
    // of type add_reducer_view<Type> and x is of type Type.  This
    // class exists to allow statements of the form v = v + x, while
    // retaining enough runtime information to detect erroneous
    // statements such as v1 = v2 + x (with v1 != v2).  In effect,
    // this class is used to transform the expression v = v + x into v
    // += x or transform v = v + x - y into v += x - y.
    class temp_sum 
    {
        friend class add_reducer_view;

	// The value of the temp_sum.
        Type m_value;	
	
	// Pointer to the view that this temp_sum object is created
	// from.
	const add_reducer_view* m_view_p;
	
        // Default copy constructor, no assignment operator
        temp_sum& operator=(const temp_sum&);

	// Construct a temp_sum from a value and a pointer to a view.
        explicit temp_sum(const Type& value,
			  const add_reducer_view<Type>* view_p);
	
      public:
        temp_sum& operator+(const Type& x);
        temp_sum& operator-(const Type& x);
    };
    
    Type m_value;

  public:
    // Value type.
    typedef Type value_type;

    /// Construct a view object with a value of 'Type()', i.e., the
    /// identity value.
    add_reducer_view();

    /// Construct a view object with the specified initial value.
    explicit add_reducer_view(const Type& value);

    /// Add 'x' to the value of this object.
    add_reducer_view& operator+=(const Type& x);

    /// Subtract 'x' from the value of this object.
    add_reducer_view& operator-=(const Type& x);

    /// Increment the value of this object using pre-increment syntax.
    add_reducer_view& operator++();   

    /// Increment the value of this object using post-increment syntax.  
    /// Because the view is not copy-constructible, it is not possible to
    /// return the previous value.
    void operator++(int);    

    /// Decrement the value of this object using pre-decrement syntax.
    add_reducer_view& operator--();    

    /// Decrement the value of this object using post-increment syntax.  
    /// Because the view is not copy-constructible, it is not possible to
    /// return the previous value.
    void operator--(int);

    /// Return a reference to the current value of this object.
    ///
    /// @warning If this method is called before the parallel calculation is
    /// complete, the value returned by this method will be a partial result.
    Type& get_value_ref();

    /// Add 'x' to the value of this view and return a temporary sum object.
    /// This temporary object can be used for additional arithmetic or
    /// assigned back to this view.
    temp_sum operator+(const Type& x) const;

    /// Subtract 'x' from the value of this view and return a temporary
    /// difference object.  This temporary object can be used for additional
    /// arithmetic or assigned back to this view.
    temp_sum operator-(const Type& x) const;    

    /// Merge the result of operators + and - into this view.  The temp_sum
    /// argument must be the result of an expression involving this same view,
    /// i.e., x = x + 5; not x = y + 5;
    add_reducer_view& operator=(const temp_sum& temp);
};


/**
 * @brief Monoid describing a summing operation on type Type.
 *
 * A monoid is a triple consisting of a type, an associative operation
 * on that type, and an identity for that operation.  For
 * add_monoid<Type>, the type is Type, the associative operation is +,
 * and the identity is Type().
 *
 * Note that for builtin integer types, the identity Type() is 0.
 */
template <typename Type>
class add_monoid : public monoid_base2<add_reducer_view<Type> >
{
public:
    /// Add the value of right to the value of left, and store the sum in
    /// left.
    static void reduce(add_reducer_view<Type>* left,
                       add_reducer_view<Type>* right);

    /// Default-initialize a Type() object into the uninitialized
    /// storage at p.
    static void identity(add_reducer_view<Type>* p);

    // Inherits from monoid_base:
    //  void destroy(int* p) const;
    //  void* allocate(size_t s) const;
    //  void deallocate(void* p) const;
};

/**
 * @brief A reducer pointer for summing values in parallel.
 *
 * This reducer pointer type is shorthand for
 * reducer_ptr<add_monoid<Type>>.
 */    
template <typename Type>
struct add_reducer_ptr : reducer_ptr< add_monoid<Type> > 
{
    /// Construct a null add_reducer_ptr.
    add_reducer_ptr();
    
    /// Construct an add_reducer_ptr whose primary object is at primary_p.
    explicit add_reducer_ptr(Type* primary_p);

    /// Construct an add_reducer_ptr that shares the same primary object as p.
    /// After construction, this hyperpointer can be used interchangeably with
    /// p.  This constructor is an implicit conversion constructor from the
    /// longhand type name.
    add_reducer_ptr(const reducer_ptr< add_monoid<Type> >& p);

    /// Make this hyperpointer share the same primary object as p.  After the
    /// assigment, this hyperpointer can be used interchangeably with p.
    add_reducer_ptr& operator=(const reducer_ptr< add_monoid<Type> >& p);
};


/////////////////////////////////////////////////////////////////////////////
// Implementation of inline and template functions
/////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------
// template class add_reducer_view<Type>::temp_sum
// -----------------------------------------------

template <typename Type>
inline 
add_reducer_view<Type>::temp_sum::temp_sum(const Type& value,
					   const add_reducer_view<Type>* view_p)
    : m_value(value), m_view_p(view_p)
{
}

template <typename Type>
inline
typename add_reducer_view<Type>::temp_sum&
add_reducer_view<Type>::temp_sum::operator+(const Type& x)
{
    m_value += x;
    return *this;
}

template <typename Type>
inline 
typename add_reducer_view<Type>::temp_sum&
add_reducer_view<Type>::temp_sum::operator-(const Type& x)
{
    m_value -= x;
    return *this;
}

// -------------------------------------
// template class add_reducer_view<Type>
// -------------------------------------

template <typename Type>
inline
add_reducer_view<Type>::add_reducer_view() : m_value()
{
}

template <typename Type>
inline
add_reducer_view<Type>::add_reducer_view(const Type& value)
    : m_value(value) 
{    
}

template <typename Type>
inline
add_reducer_view<Type>&
add_reducer_view<Type>::operator+=(const Type& x) 
{
    m_value +=x;
    return *this;
}

template <typename Type>
inline
add_reducer_view<Type>&
add_reducer_view<Type>::operator-=(const Type& x) 
{
    m_value -=x;
    return *this;
}

template <typename Type>
inline
add_reducer_view<Type>&
add_reducer_view<Type>::operator++()
{
    m_value += 1;
    return *this;
}

template <typename Type>
inline
void
add_reducer_view<Type>::operator++(int)
{
    m_value += 1;
}

template <typename Type>
inline
add_reducer_view<Type>&
add_reducer_view<Type>::operator--()
{
    m_value -= 1;
    return *this;
}

template <typename Type>
inline
void
add_reducer_view<Type>::operator--(int)
{
    m_value -= 1;
}

template <typename Type>
inline
Type& add_reducer_view<Type>::get_value_ref()
{
    return m_value;
}
       
template <typename Type>
inline
typename add_reducer_view<Type>::temp_sum
add_reducer_view<Type>::operator+(const Type& x) const
{
    return temp_sum(x, this);
}

template <typename Type>
inline
typename add_reducer_view<Type>::temp_sum
add_reducer_view<Type>::operator-(const Type& x) const
{
    return temp_sum(-x, this);
}

template <typename Type>
inline
add_reducer_view<Type>&
add_reducer_view<Type>::operator=(const temp_sum& temp)
{
    __CILKRTS_ASSERT(temp.m_view_p == this);
    m_value += temp.m_value;
    return *this;
}

// -------------------------------
// template class add_monoid<Type>
// -------------------------------

template <typename Type>
void
add_monoid<Type>::reduce(add_reducer_view<Type>* left,
			 add_reducer_view<Type>* right) 
{
    *left += right->get_value_ref();
}

template <typename Type>
void
add_monoid<Type>::identity(add_reducer_view<Type>* p) 
{
    ::new((void*)p) add_reducer_view<Type>();
}


// ------------------------------------
// template class add_reducer_ptr<Type>
// ------------------------------------

template <typename Type>
inline
add_reducer_ptr<Type>::add_reducer_ptr() 
    : reducer_ptr< add_monoid<Type> >()
{
}

template <typename Type>
inline
add_reducer_ptr<Type>::add_reducer_ptr(Type* primary_p)
    : reducer_ptr< add_monoid<Type> >(primary_p)
{    
}

template <typename Type>
inline
add_reducer_ptr<Type>::add_reducer_ptr(const reducer_ptr< add_monoid<Type> >& p)
    : reducer_ptr< add_monoid<Type> >(p)
{    
}

template <typename Type>
inline
add_reducer_ptr<Type>&
add_reducer_ptr<Type>::operator=(const reducer_ptr< add_monoid<Type> >& p)
{
    reducer_ptr< add_monoid<Type> >::operator=(p);
    return *this;
}
 
} // namespace cilk

#endif /*  ADD_REDUCER_H_INCLUDED */
